<!DOCTYPE HTML>

<!-- 
Strata by HTML5 UP
html5up.net | @n33co
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
	<head>
		<title>Binary tree traversal &middot; Blog for Ysc</title>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />
		<meta name="author" content="Your name">
		<meta name="description" content="Describe your website">
		<meta http-equiv="content-language" content="en-us" />

		
		<meta name="og:site_name" content="Blog for Ysc">
		<meta name="og:title" content="Binary tree traversal">
		<meta name="og:url" content="https://yeeeesc.gitee.io/post/binary-tree-traversal/">
		
		<meta name="og:image" content="https://yeeeesc.gitee.io/images/avatar.jpg">
		
		

		<meta name="generator" content="Hugo 0.69.2" />

		<!--[if lte IE 8]><script src='https://yeeeesc.gitee.io/js/ie/html5shiv.js'></script><![endif]-->
		<link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
		<link rel="stylesheet" href="https://yeeeesc.gitee.io/css/main.css" />
		<!--[if lte IE 8]><link rel="stylesheet" href="https://yeeeesc.gitee.io//css/ie8.css"><![endif]-->

		
		
	</head>

	<body id="top">
		<!-- Header -->
<header id="header">
	
	<a href="https://yeeeesc.gitee.io/" class="image avatar"><img src="https://yeeeesc.gitee.io/images/avatar.jpg" alt="" /></a>
	
	
		<h1><strong>I&rsquo;m Strata</strong>, a super simple<!-- raw HTML omitted --> responsive site template freebie<!-- raw HTML omitted --> crafted by <a href="//html5up.net">HTML5 UP</a>.</h1>
	

	
		<nav id="sidebar">
			<ul>
			
				<li><a href="https://yeeeesc.gitee.io/">Home</a></li>
			
				<li><a href="https://yeeeesc.gitee.io/post/">Blog</a></li>
			
			</ul>
		</nav>
	
</header>


		<!-- Main -->
		<div id="main">
			
	<span>
		<h1>Binary tree traversal</h1>

		<i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-27 13:39:46 &#43;0200 &#43;0200">2020-10-27</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/algorithm">Algorithm</a>
        
        
    



   
   


	</span>

	<p>
	    <h3 id="part-1-preorder">Part 1. Preorder</h3>
<pre><code>class Solution {
public:
    vector&lt;int&gt; preorderTraversal(TreeNode* root) {
        vector&lt;int&gt; ans;
        if (!root)  return ans;
        stack&lt;TreeNode*&gt; s;
        s.push(root);
        while (!s.empty()){
            TreeNode* Top = s.top();
            s.pop();
            ans.push_back(Top-&gt;val);
            if (Top-&gt;right) s.push(Top-&gt;right);
            if (Top-&gt;left)  s.push(Top-&gt;left);
        }
        return ans;
    }
};
</code></pre><h3 id="part-2-inorder">Part 2. Inorder</h3>
<pre><code>class Solution {
public:
    vector&lt;int&gt; inorderTraversal(TreeNode* root) {
        vector&lt;int&gt; ans;
        if (!root)   return ans;
        stack&lt;TreeNode*&gt; stk;
        while (!stk.empty() || root){
            while (root){
                stk.push(root);
                root = root-&gt;left;
            }
            root = stk.top();
            stk.pop();
            ans.push_back(root-&gt;val);
            root = root-&gt;right;
        }
        return ans;
    }
};
</code></pre><h3 id="step-3-postorder">Step 3. Postorder</h3>
<pre><code>class Solution {
public:
    vector&lt;int&gt; postorderTraversal(TreeNode* root) {
        vector&lt;int&gt; ans;
        if (!root)  return ans;
        stack&lt;TreeNode*&gt; stk;
        TreeNode* prev = nullptr;
        stk.push(root);
        while (!stk.empty() || root){
            while (root &amp;&amp; root-&gt;left){
                stk.push(root-&gt;left);
                root = root-&gt;left;
            }
            root = stk.top();
            stk.pop();
            if (!root-&gt;right || root-&gt;right == prev){
                ans.push_back(root-&gt;val);
                prev = root;
                root = nullptr;
            }
            else {
                stk.push(root);
                stk.push(root-&gt;right);
                root = root-&gt;right;
            }
        }
        return ans;
    }
};
</code></pre><h3 id="step-4-复杂度分析">Step 4. 复杂度分析</h3>
<ul>
<li>时间复杂度：<code>O(n)</code>，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。</li>
<li>空间复杂度：<code>O(n)</code>，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。</li>
<li>时空复杂度同递归模式相同</li>
</ul>

	</p>

	<div id="disqus_thread"></div>
<script type="application/javascript">
    var disqus_config = function () {
    
    
    
    };
    (function() {
        if (["localhost", "127.0.0.1"].indexOf(window.location.hostname) != -1) {
            document.getElementById('disqus_thread').innerHTML = 'Disqus comments not available by default when the website is previewed locally.';
            return;
        }
        var d = document, s = d.createElement('script'); s.async = true;
        s.src = '//' + "spf13" + '.disqus.com/embed.js';
        s.setAttribute('data-timestamp', +new Date());
        (d.head || d.body).appendChild(s);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

		</div>

		<!-- Footer -->
<footer id="footer">
	<ul class="icons">
		
		
		
		<li><a href="//twitter.com/spf13" target="_blank" class="icon fa-twitter"><span class="label">Twitter</span></a></li>
		
		
		<li><a href="//github.com/spf13" target="_blank" class="icon fa-github"><span class="label">GitHub</span></a></li>
		
		
		<li><a href="//gitlab.com/spf13" target="_blank" class="icon fa-gitlab"><span class="label">GitLab</span></a></li>
		
		
		
		
		
		<li><a href="https://yeeeesc.gitee.io/#contact-form" class="icon fa-envelope-o"><span class="label">Email</span></a></li>
		
		
		<li><a href="https://yeeeesc.gitee.io/index.xml" class="icon fa-rss" type="application/rss+xml"><span class="label">RSS</span></a></li>
		
	</ul>

	<ul class="copyright">
		
		<li>© John Doe</li>
		
		<li>Design: <a href="//html5up.net">HTML5 UP</a></li>
		
		<li>Demo Images: <a href="//unsplash.com/">Unsplash</a></li>
		
	</ul>
</footer>

<!-- Scripts -->
<script src="https://yeeeesc.gitee.io/js/jquery.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/jquery.poptrox.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/skel.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/util.js"></script>

<script src="https://yeeeesc.gitee.io/js/main.js"></script>





	</body>
</html>
